day19 - Santa's Signature

Can you forge Santa's signature?

Service: nc 3.93.128.89 1219
Download: santas_signature.tar.gz

Recon

The service wants us to prove that we're Santa by signing some messages that can be verified under a specific, given RSA key. The given code indicates that the key is a 4096-bit RSA key, generated randomly using a proper CSPRNG. There's probably nothing interesting about that. The interesting part, however, is that it's performing the verification operation without any armoring (padding) scheme, say RSA-OAEP or PKCS #1 v1.5.

It expects us to give it 3 distinct messages with their signatures, and if all of them pass the signature verification check, then we're given the flag.

The idea is pretty straightforward and relies on the fact that RSA encryption/decryption (and similarly, verification/signature) is an exponentiation operation in a multiplicative group of integers modulo $n$, the modulus.

Recall that RSA encryption is defined for the parameters $n$ - the modulus, $m$ - the message, and $e$ - the public exponent as:

$$c = m^e \mod n$$

where $c$ is the encrypted message. For signature verification, we perform the same operation, then we check that the resulting $c$ is equal to the signed message $m$, or a transformation of it for a chosen armoring scheme.

Under these operations, there are some "special" messages do not get changed, such as $0$, which encrypts/decrypts to $0$. Additionally, $1$ also does not change in any way. Both these cases are trivial $0^x = 0$ and $1^x = 1$ for any $x \in \mathbb{Z^{+}}$.

One more such message is $n-1$ where $n$ is the modulus of the key under which verification will be done. To see why that is the case, let's unpack what happens when we raise $n-1$ to the second power modulo $n$:

$$ \begin{align*} & (n - 1)^2 &\mod n \\ &= n^2 - 2n + 1 &\mod n \\ &= 0 - 0 + 1 &\mod n \\ &= 1 \end{align*} $$

That is because $n^2$ and $2n$ are multiples of $n$, which are congruent to $0 \mod n$. This would lead us to realizing that $(n - 1)^x \mod n$ for $x \geq 2$ is either $1 \mod n$ if $x$ is even or $n-1 \mod n$ if $x$ is odd.

Therefore, given the RSA context and knowing that the public and private exponents $e$ and $d$ must be odd (the reason why they must be odd is left as an exercise to the reader), we can immediately infer that the "encryption" or "decryption" of $n - 1$ is just $n - 1$. And that would be our third and final message necessary to fool the code.

Code

#!/usr/bin/env python3
import Crypto
from Crypto.PublicKey import RSA
import sys

try:
    with open("key",'r') as f:
        key = RSA.importKey(f.read())
except:
    rng = Crypto.Random.new().read
    key = RSA.generate(4096, rng)
    with open("key",'w') as f:
        f.write(key.exportKey().decode("utf-8"))

def h2i(h):
    try:
        return int(h,16)
    except Exception:
        print("Couldn't hex decode",flush=True)
        sys.exit()

header = \
"""Dear Santa,
Last christmas you gave me your public key,
to confirm it really is you please sign three
different messages with your private key.

Here is the public key you gave me:"""
print(header,flush=True)
print(key.publickey().exportKey().decode("utf-8"),flush=True)
ms = []

for i in range(1,4):
    m = h2i(input("Message %d you signed (hex encoded):" % i))
    if m in ms:
        print("I said different messages!",flush=True)
        sys.exit()
    s = [h2i(input("Signature %d:" % i))]
    if not key.verify(m,s):
        print("Looks like you aren't Santa after all!",flush=True)
        sys.exit()
    ms.append(m)

print("Hello Santa, here is your flag:",flush=True)
with open("flag",'r') as flag:
    print(flag.read(),flush=True)

Exploit

from pwn import *
from Crypto.PublicKey import RSA


def send_msg(e, msg, sig):
    e.recvuntil(':')
    e.sendline(msg)
    e.recvuntil(':')
    e.sendline(sig)


e = remote("3.93.128.89", 1219)
e.recvuntil("Here is the public key you gave me:")
pubkey = e.recvuntil("-----END PUBLIC KEY-----").strip()

key = RSA.importKey(pubkey)
n = hex(key.key.n - 1)

send_msg(e, '00', '00')
send_msg(e, '01', '01')
send_msg(e, n, n)

print(e.recvline())
print(e.recvline())

Flag

$ python exploit.py
b'Hello Santa, here is your flag:\n'
b'AOTW{RSA_3dg3_c4s3s_ftw}\n'